#include "attraction.h"
#include "ui_attraction.h"
#include "path.h"
#include <QPainter>
#include <QMessageBox>
#include <QMouseEvent>
#include <QCloseEvent>
#include <QDialog>
#include <QRegExpValidator>
#include <QDebug>

#define num 15
#define Max 40

mgraph initgraph();

int allpath(mgraph c,int start,int end);
void path(mgraph c,int m,int n,int k);
QString transtring;

mgraph campus;          //图
int d[20];
int visited[20];
int shortest[MaxVertexNum][MaxVertexNum];    //最短路径
int pathn[MaxVertexNum][MaxVertexNum];       //存储路径


attraction::attraction(QWidget *parent) :
    QMainWindow(parent),
    ui(new Ui::attraction)
{
   // ui->setupUi(this);
    campus = initgraph();
    //限制用户输入
    QRegExp regx("\\d{2}");
    QValidator* validator = new QRegExpValidator(regx, this);

    ui->setupUi(this);
    ui->Start->setValidator(validator);
    ui->End->setValidator(validator);
}

attraction::~attraction()
{
    delete ui;
}

int locatevex(mgraph c,int v);

void attraction::on_alterButton_clicked()
{
    int start = ui->Start->text().toInt();// 获取起点位置
    int end = ui->End->text().toInt();    // 获取终点位置

    ui->alternativePath->clear();

    if ((start > 0 and start < 16) and (end > 0 and end < 16)) 
    {
        allpath(campus, start, end);     // 可选路径搜索
    }
    else
    {
        ni=new search_error;
        ni->show();
    }
}

void attraction::on_shortestButton_clicked()
{    QString s=ui->Start->text();
     QString f=ui->End->text();
    int start = ui->Start->text().toInt(); // 获取起点位置
    int end = ui->End->text().toInt();    // 获取终点位置
    ui->shortestPath->clear();
     if(start!=end)
    {
      if ((start > 0 and start < 16) and (end > 0 and end < 16))
     {
        shortestpath(campus, start, end);
     }
      else
    {
        ni=new search_error;
        ni->show();
    }
    }
    else
    {  if(f==""||s=="")
         {
             ni=new search_error;
             ni->show();
         }
         else{
        transtring.append(QString::number(end));
        ui->shortestPath->append(transtring);
        ui->shortestPath->append("最短路线长为" + QString::number(0));
        transtring.clear();}
    }
}


//图初始化
mgraph initgraph()
{
    int i,j;
    mgraph c;
    c.vexnum=15;            // 顶点个数，即地点个数
    c.arcnum=22;            // 边的个数，即路径个数

    for(i=1; i<=num; i++)   // 依次设置景点编号
    {
      c.vexs[i].position = i;
    }

    strcpy(c.vexs[1].name,"武汉大学牌坊");
    strcpy(c.vexs[2].name,"樱花大道");
    strcpy(c.vexs[3].name,"万林艺术博物馆");
    strcpy(c.vexs[4].name,"鉴湖");
    strcpy(c.vexs[5].name,"宋卿体育馆");
    strcpy(c.vexs[6].name,"老图书馆");
    strcpy(c.vexs[7].name,"理学楼");
    strcpy(c.vexs[8].name,"九一二操场");
    strcpy(c.vexs[9].name,"行政楼");
    strcpy(c.vexs[10].name,"梅园小操场");
    strcpy(c.vexs[11].name,"鲲鹏广场");
    strcpy(c.vexs[12].name,"珞珈广场");
    strcpy(c.vexs[13].name,"半山庐");
    strcpy(c.vexs[14].name,"星湖");
    strcpy(c.vexs[15].name,"凌波门");

    for (i=1; i<=num; i++)
    {
      for (j=1;j<=num;j++)
      {
        c.arcs[i][j].dis=10000;
      }
      c.arcs[1][12].dis=380;
      c.arcs[1][14].dis=1100;
      c.arcs[2][6].dis=100;
      c.arcs[2][11].dis=280;
      c.arcs[2][7].dis=190;
      c.arcs[3][4].dis=230;
      c.arcs[3][5].dis=280;
      c.arcs[3][9].dis=440;
      c.arcs[3][12].dis=370;
      c.arcs[3][13].dis=900;
      c.arcs[4][10].dis=180;
      c.arcs[4][11].dis=200;
      c.arcs[5][11].dis=10;
      c.arcs[5][12].dis=600;
      c.arcs[6][7].dis=270;
      c.arcs[7][8].dis=60;
      c.arcs[7][10].dis=190;
      c.arcs[7][15].dis=690;
      c.arcs[8][9].dis=120;
      c.arcs[9][10].dis=300;
      c.arcs[9][13].dis=300;
    }

    for(i=1;i<=num;i++)
    {
      for(j=1;j<=num;j++)
      {
        c.arcs[j][i].dis=c.arcs[i][j].dis;
      }
    }
    return c;
}

//查找景点编号
int locatevex(mgraph c,int v)
{
    int i;
    for (i=1;i<=c.vexnum;i++)
      if (v==c.vexs[i].position)  return i;  // 找到，返回顶点序号i
    return -1;  // 没有找到该顶点
}

//查找景点路径
void attraction::path(mgraph c, int m, int n, int k)
{
    int s;
    int t=k+1;                  // t用于存放路径上下一个顶点对应的d[]数组元素的下标
    int  length=0;
    if (d[k] == n)                                     // 若d[k]是终点n则输出该路径
    {
        for (s=0; s<k; s++)
        {
            length = length+c.arcs[d[s]][d[s+1]].dis;   // 计算路径长度
        }

        if (length <= 10000)
        {
            for (s=0; s<k; s++)
            {
                transtring.append(QString::number(c.vexs[d[s]].position) + "-->"); // 输出该路径 s=0时为起点m
            }
            transtring.append(QString::number(c.vexs[d[s]].position));   // 输出最后一个景点名
            ui->alternativePath->append(transtring);
            ui->alternativePath->append("总路线长为" + QString::number(length));
         }
            transtring.clear();
    }
    else
    {
        s = 1;
        while (s <= c.vexnum)
        {                                       // 从第m个顶点，试探所有顶点是否有路径
            if ((c.arcs[d[k]][s].dis<10000) && (visited[s]==0))
            {  // 顶点m到顶点s有边且未被访问
                visited[s]=1;
                d[k+1]=s;       // 存储顶点编号
                path(c,m,n,t);
                visited[s]=0;   // 将找到的路径上顶点的访问标志重新设置为0
            }
            s++;    // 试探从下一个顶点s开始是否有到终点的路径
        }
    }
}

//查找两点间路径
void attraction::allpath(mgraph c, int start, int end)
{
    int k, m, n;
    m=locatevex(c, start);   //用 locatevex 确定该顶点是否存在。若存在，返回该顶点编号。
    n=locatevex(c, end);
    d[0] = m;                 // 存储路径起点m

    for (k=0; k<num; k++)
    {    // 全部顶点访问标志初值设为0
      visited[k] = 0;
    }
    visited[m] = 1;           // 第m个顶点访问标志设置为1
    path(c, m, n, 0);          // k=1，对应起点d[1]==m k为d[]数组下标
}

//两点间最短距离
void attraction::shortestpath(mgraph c, int start, int end)
{
    int i, j;
    i = start;
    j = end;
    floyd(c);   // floyd算法
    transtring.append(QString::number(start) + "-->");
    while (pathn[start][end] != end)
    {
        transtring.append(QString::number(pathn[start][end]) + "-->");
        start = pathn[start][end];
    }
    transtring.append(QString::number(end));
    ui->shortestPath->append(transtring);
    ui->shortestPath->append("最短路线长为" + QString::number(shortest[i][j]));
    transtring.clear();
}

//弗洛伊德算法
void attraction::floyd(mgraph c)
{
    for (int i=1; i<=num; i++)
    {                  // 将图的邻接矩阵赋值给shortest二维数组
        for (int j=1; j<=num; j++)
        {
            shortest[i][j] = c.arcs[i][j].dis;
            pathn[i][j] = j;
        }
    }
    for (int k=1; k<=num; k++)
    {
        for (int i=1; i<=num; i++)
        {
            for (int j=1; j<=num; j++)
            {
                if (shortest[i][j] > shortest[i][k]+shortest[k][j])
                {
                    shortest[i][j] = shortest[i][k]+shortest[k][j];
                    pathn[i][j] = pathn[i][k];   // 记录一下所走的路，P数组用来存放前驱顶点
                }
             }
        }
    }
}




